\section{Lower bound proof for the triangulation process}
\label{app:triangulation}
\begin{LabeledProof}{Theorem~\ref{thm:tri+lower-10p}}
  We first observe that during the triangulation process there is a 
  time $t$ when the number of missing edges is at least $m = O(\sqrt{k})$
  and the minimum degree is at least $n/3$. If $k<\frac{2}{3} n$ then 
  this is true initially and for larger $k$ this is true at the first 
  time $t$ the minimum degree is large enough. The second case follows since
  the degree of a node (and thus also the minimum degree) can at most
  double in each step guaranteeing that the minimum degree is not larger
  than $\frac{2}{3}n$ at time $t$ also implying that at least $\frac{n}{3} = \Omega(\sqrt{k})$
  edges are still missing. 
  
  Given the bound on the minimum degree any missing edge $\{u,v\}$ is added 
  by a fixed node $w$ with probability at most $\frac{9}{2n^2}$.
  Since there are at most $n-2$ such nodes the probability that a missing edge
  gets added is at most $\frac{9}{2n}$. To analyze the time needed for all missing
  edges to be added we denote with $X_i$ the random variable
  counting the number of steps needed until the $i$th of the $m$ missing edges is added.
  We would like to analyze $\prob{X_1\le T, X_2\le T, \dots, X_m \le T}$ for an 
  appropriately chosen number of steps $T$. Note that the
  events $X_i < T$ and $X_j <T$ are not independent and indeed can be positively
  or negatively correlated. Nevertheless, independent of the conditioning onto 
  any of the events $X_j < T$, we have that $\prob{X_1 \le T} \leq 1 - (1 - \frac{9}{2n})^T \leq 1 - \frac{1}{\sqrt{m}}$ for an appropriately chosen $T = \Omega(n \log m)$, where $m$ is again the number of missing edges at time $t$. Thus,
$$\prob{X_1\le T, X_2\le T, \dots, X_m \le T} =$$
$$= \prob{X_1\le T| X_2\le T, \dots, X_m \le T} \cdot \prob{X_2 \le T | X_3, \dots, X_m \le T} \cdot \ldots \cdot \prob{X_m \le T} $$
$$\leq \rb{1-\frac{1}{\sqrt{m}}}^m \; = \; O\rb{e^{-\sqrt{m}}} \; = \; O\rb{e^{-k^{1/4}}}$$

This shows that the triangulation process takes with probability at
least $1-O\rb{e^{-k^{1/4}}}$ at least $\Omega(n \log m) = O(n \log k)$
steps to complete.
\end{LabeledProof}
